//
// Created by francklinson on 2021/11/24 AT 11:09.
// May Saint Diana bless you!
//

#include <iostream>
#include <vector>
#include <unordered_map>
#include <unordered_set>
#include <queue>
#include <algorithm>
#include <functional>
#include <climits>
#include <string>

using namespace std;

class Solution {
public:
    unordered_set<int> prime{2, 3, 5, 7, 11, 13, 17, 19};

    int countPrimeSetBits(int left, int right) {
        int ans = 0;
        for (int i = left; i <= right; ++i) {
            if (primeCheck(i))
                ++ans;
        }
        return ans;
    }

    /**
     * 统计x中1的位数是不是一个质数
     * @param x
     * @return
     */
    bool primeCheck(int x) {
        int ans = 0;
        while (x) {
            ans += x & 1;
            x >>= 1;
        }
//        ans = __builtin_popcount(x);  // gcc私有
        return prime.count(ans);
    }
};

int main() {
    Solution solution;
    cout << solution.countPrimeSetBits(6, 10) << endl;
    cout << solution.countPrimeSetBits(10, 15) << endl;
    return 0;
}

